package alibaba.test;

import pojo.ListNode;
import utils.PrintUtil;

import javax.swing.*;
import java.util.*;

/**
 * @Author chengshijian
 * @Date 2022/3/17 21:35
 */
public class Solution {

    /**
     * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
     * <p>
     * <p>
     * <p>
     * 示例：
     * <p>
     * 输入：nums = [1,2,3,4]
     * 输出：[1,3,2,4]
     * 注：[3,1,2,4] 也是正确的答案之一。
     * <p>
     * <p>
     * 提示：
     * <p>
     * 0 <= nums.length <= 50000
     * 0 <= nums[i] <= 10000
     * 通过次数250,742提交次数387,929
     *
     * @param nums
     * @return
     */
    public static int[] exchange(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            while (i < j && (nums[i] & 1) == 1) {
                i++;
            }
            while (i < j && (nums[j] & 1) == 0) {
                j--;
            }
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    private static int max = Integer.MIN_VALUE;

    /**
     * 超时
     *
     * @param nums
     * @return
     */
    public static int maximumProduct2(int[] nums) {
        backTrack(new ArrayList<>(), nums);
        return max;
    }

    private static void backTrack(List<Integer> pathList, int[] nums) {
        if (pathList.size() == 3) {
            int a = nums[pathList.get(0)];
            int b = nums[pathList.get(1)];
            int c = nums[pathList.get(2)];
            int r = a * b * c;
            if (r > max) {
                max = r;
            }
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!pathList.contains(i)) {
                    pathList.add(i);
                    backTrack(pathList, nums);
                    pathList.remove(Integer.valueOf(i));
                }
            }
        }
    }

    /**
     * 628. 三个数的最大乘积
     * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,3]
     * 输出：6
     * 示例 2：
     * <p>
     * 输入：nums = [1,2,3,4]
     * 输出：24
     * 示例 3：
     * <p>
     * 输入：nums = [-1,-2,-3]
     * 输出：-6
     * <p>
     * <p>
     * 提示：
     * <p>
     * 3 <= nums.length <= 104
     * -1000 <= nums[i] <= 1000
     * 通过次数89,336提交次数170,361
     *
     * @param nums
     * @return
     */
    public static int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
    }

    /**
     * 142. 环形链表 II
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * <p>
     * 不允许修改 链表。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * <p>
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：返回索引为 1 的链表节点
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * 示例 2：
     * <p>
     * <p>
     * <p>
     * 输入：head = [1,2], pos = 0
     * 输出：返回索引为 0 的链表节点
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * 示例 3：
     * <p>
     * <p>
     * <p>
     * 输入：head = [1], pos = -1
     * 输出：返回 null
     * 解释：链表中没有环。
     * <p>
     * <p>
     * 提示：
     * <p>
     * 链表中节点的数目范围在范围 [0, 104] 内
     * -105 <= Node.val <= 105
     * pos 的值为 -1 或者链表中的一个有效索引
     * <p>
     * <p>
     * 进阶：你是否可以使用 O(1) 空间解决此题？
     * <p>
     * 通过次数393,442提交次数705,217
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (slow == fast) {
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{0, 0, 0};
        System.out.println(maximumProduct(arr));
    }
}


class CQueue {

    private Stack<Integer> in;
    private Stack<Integer> out;

    public CQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    public void appendTail(int value) {
        in.push(value);
    }

    public int deleteHead() {
        try {
            tryEnsureNotEmpty();
            return out.pop();
        } catch (EmptyStackException e) {
            return -1;
        }
    }

    private void tryEnsureNotEmpty() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }
}

